1. Field of the Invention
The present invention relates to the testing of integrated circuits and, in particular, to a built in self test (BIST) technique for determining the existence of "stuck at faults" in multiplier, adder, or subtractor implementations by pseudo-exhaustively exercising all permutations of inputs and outputs. The technique is scalable to any size.
2. Discussion of the Related Art
In a production testing environment, the testing of semiconductor devices is performed to separate good devices from bad devices. Data collected from a test program may be used for yield enhancement. This is done by finding marginal areas of the device design or in the fabrication process and then making improvements to raise yields and therefore lower cost. The basis for all testing of complex integrated circuits is the comparison of known correct output patterns to the response of a device under test. The simulation of the device design is typically done with input stimuli which fully exercise the design and therefore verify the correctness of the design. After fabrication of the design, often the same stimuli (also called test vectors) are presented to each device under test to separate good devices from defective devices. Comparisons are made cycle by cycle with an option to ignore certain pins, times, or patterns. If the device response and the expected response are not in agreement, the devices are usually considered defective.
Built-In Self-Testing (BIST) is the implementation of logic built into the circuitry to do testing without the use of an external tester for pattern generation and comparison purposes. An external tester is still needed to categorize failures and to separate good units from bad units. In this case, the external tester supplies clocks to the device and determines pass/fail from the outputs of the device. The test vectors are generated and input to the device under test, and a resulting signature is generated. The signature can be a simple pass or fail signal presented on one pin of the part, or the signal may be a polynomial generated during the self-testing. Usually, if a polynomial is used, it has some significance to the actual states of the part.
Self-testing capability can be implemented on virtually any size logic block. However, there are tradeoffs between the extra logic added to implement the self-testing capability and the inherent logic of the block to be tested. Often, the self-test logic adds not only extra hardware to the design, but also adds latency to the logic block having the self-test even under normal operations.
Many Built In Self Test (BIST) arrangements deal with embedded memory structures like Random Access Memories (RAMs). These arrangements usually tend to be implementation dependent and have rather complicated arrangements for generating data and predicting failures. In many cases, a signature is collected for analysis after a series of stimuli has been applied to the block being tested. Many BIST arrangements do not have the flexibility to be implemented with either software alone or hardware alone or a mixture of both. FIG. 2 depicts a typical self-test circuit. The logic block under test 201 has N independent logic inputs. An N-bit counter sequentially steps through all 2.sup.N unique input permutations. However, if it is desired for the self-test time to be less than about one second, N is typically limited to about twenty. The logic block under test has M output bits. An M-bit flip-flop 203 latches the output of after the first set of stimuli have been applied. Each subsequent M-bit output of the logic block is exclusive ORed with the contents of the flip-flop 203 such that at the end of the self-test, an M-bit signature is available as the output of the flip-flop 203. An exclusive OR 204 or exclusive NOR function is typically used because the its output value is always dependent upon all of the inputs. Therefore, if any single output of the logic block under test is incorrect, the final signature will be incorrect. (In contrast, a two-input AND function, for example, does not produce the same input-output dependence. For example, if one input of the AND function is zero, then the value of the other input does not influence the output at all.)
Direct access testing is alternative to direct access testing whereby an external tester gains access to a device logic block by bringing signals from the block to the outside world via multiplexors. Input test vectors are directly supplied to the logic block by the external tester, and then the outputs are directly measured by the tester. This is one of the simplest methods for checking devices for logical functionality. Often, direct access testing supplements previous testing methods by allowing the user to impose input data patterns directly on large blocks of logic which would not otherwise be directly accessible. Using direct access testing, entering a special test mode would force certain logic blocks via multiplexors to gain access to the outside pins of the part, and to measure the access, status, and logical functionality of the block directly.
Fault grading is a measure of test coverage of a given set of stimuli and responses for a given circuit. This figure of merit is used to ensure that the device is fully testable and measurable. Typically, once the test patterns are developed for the device, artificial faults are put into the design via simulation to ensure that the part is fully testable and observable.
A "stuck-at fault" may be caused by a variety of conditions, although the defining characteristic of a stuck-at fault is that a circuit node is undesirably immovable from certain logic value (either zero or one) regardless of any circuit conditions. FIG. 1 illustrates a single stuck-at-one fault 104 injected into a simple logic circuit with an exhaustive set of input data patterns for fully checking the functionality of the logic circuit. Even though the stuck-at-one fault 104 exists at an internal node which is not directly observable, the stuck-at-one fault 104 shows up on at the output Z of the circuit. Gaining high fault coverage is a very desirable method for ensuring that the tested devices will function correctly in a system. Ideally, all internal nodes should be tested for stuck-at-zero and stuck-at-one faults.
Although fault grading using single stuck-at-zero and single-stuck-at-one faults covers many types of semiconductor failures, it does not cover all of them. For example, bridging faults and intermittent faults are two other common types of faults which occur in semiconductor devices.
Data patterns that were generated during simulation are often converted into a functional production test program. The cost of production testing is very much related to test time per device. In production, package handlers, wafer probe equipment, people, and often a computer network are needed to run production tests.
One effective way to test a circuit 100 for single stuck-at faults is to exhaustively check all outputs of the circuit for correctness for all possible input permutations. For the circuit shown in FIG. 1, this is a relatively straightforward procedure which requires only sixteen separate operations of the circuit. In general, for a circuit having N inputs, 2.sup.N operations of the circuit are required to exhaustively test the circuit using all possible input permutations. This is feasible for smaller circuits; however, because the number of input permutations increases exponentially with N, exhaustively testing all 2.sup.N input permutations becomes prohibitively time consuming.
As feature sizes for semiconductor manufacturing processes become smaller, bus widths become larger. Thirty-two and sixty-four bit internal busses are commonplace today. Similarly, the widths of the arithmetic units and mathematical functions become larger. Hardware multipliers, dividers, square root modules, adders, and subtractors supporting thirty-two and sixty-four-bit operands currently are available.
Moreover, in the field of cryptography, there is demand for specialized hardware to support asymmetric encryption/decryption algorithms such as the RSA algorithm. (See, for example, U.S. Pat. No. 4,405,829 for a description of the RSA algorithm.) Such encryption algorithms typically require many multiplications of very large numbers. If very large multipliers are implemented in hardware, the testing of those multipliers offers significant challenges. For example, if it is assumed that a multiplication requires 1 nanosecond regardless of the size of the operands (a generously low estimate), an exhaustive test of a 8-bit multiplier requires only 65.5 microseconds, an exhaustive test of a 16-bit multiplier requires only 4.3 seconds, but an exhaustive test of a 32-bit multiplier would require about 584.9 years, while an exhaustive test of a 256-bit multiplier would require about 10.sup.146.6 years. This is approximately 10.sup.136.6 times greater than the estimated age of the universe (assuming that the age of the universe is 10 billion years). This demonstrates that an exhaustive test of mathematical functions in a manner such as shown in FIG. 1 is totally infeasible.
It is clear from the above discussion that there is a need for testing semiconductor circuits implementing math functions such that all internal nodes are checked for stuck-at faults without performing an exhaustive test of all possible input permutations.